package com.base.dp;

public class Change {
    public static void main(String[] args) {
        Change change = new Change();
        System.out.println(change.change(5, new int[]{1, 2, 5}));
    }

    /**
     * 定义状态：设 dp[i] 表示凑成金额 i 的硬币组合数。
     * 状态初始化：dp[0] = 1，因为凑成金额 0 的组合有一种，即不使用任何硬币。
     * 状态转移方程：对于每个硬币 coins[j]（其中 j 是硬币的索引），我们需要更新 dp[i] 的值。状态转移方程如下：
     * dp[i] = dp[i] + dp[i - coins[j]]
     * 这个方程的意思是，凑成金额 i 的组合数等于不使用当前硬币 coins[j] 的组合数加上使用至少一个 coins[j] 硬币的组合数。
     * 遍历顺序：我们需要确保在计算 dp[i] 时，所有 dp[i - coins[j]] 已经被计算过。因此，我们应该先遍历硬币，然后从硬币面额开始遍历到总金额。
     * @param amount 金额
     * @param coins  硬币63
     * @return 组合数
     */
    public int change(int amount, int[] coins) {
        //设 dp[i] 表示凑成金额 i 的硬币组合数。
        int[] dp = new int[amount + 1];
        dp[0] = 1; // 初始化 因为凑成金额 0 的组合有一种，即不使用任何硬币
        // 遍历所有硬币
        for (int coin : coins) {
            // 更新 dp 数组
            for (int i = coin; i <= amount; i++) {// coin = 2 ;amount = 5  i = 2,3,4,5
                //状态转移方程：对于每个硬币 coins[j]（其中 j 是硬币的索引），我们需要更新 dp[i] 的值。状态转移方程如下：
                //     * dp[i] = dp[i] + dp[i - coins[j]]
                //这个方程的意思是，凑成金额 i 的组合数等于不使用当前硬币 coins[j] 的组合数加上使用至少一个 coins[j] 硬币的组合数。
                //     * 遍历顺序：我们需要确保在计算 dp[i] 时，所有 dp[i - coins[j]] 已经被计算过。因此，我们应该先遍历硬币，然后从硬币面额开始遍历到总金额。
                dp[i] += dp[i - coin];//   dp[2],dp[3],dp[4],dp[5]           dp[0],dp[1],dp[2],dp[3]
            }
        }
        return dp[amount];
    }
}
